package com.xyhuo.leetcode.december;

import java.util.ArrayList;
import java.util.List;

/**
 * 单词搜索
 * https://leetcode.cn/problems/word-search/
 *
 * @time 2023/12/28
 */
public class Exist {

//    public static void main(String[] args) {
//        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        Exist e = new Exist();
//        e.exist(board, "ABCCED");
//    }

    public boolean exist(char[][] board, String word) {
        charArray = word.toCharArray();
        List<int[]> first = new ArrayList<>();
        m = board.length;
        n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (charArray[0] == board[i][j]) {
                    int[] firstItem = new int[2];
                    firstItem[0] = i;
                    firstItem[1] = j;
                    first.add(firstItem);
                }
            }
        }
        if (first.isEmpty()) {
            return false;
        }
        int[][] exist = new int[m][n];
        for (int[] index : first) {
            exist[index[0]][index[1]] = 1;
            dfs(board, exist, index[0], index[1], 0);
            exist[index[0]][index[1]] = 0;
        }
        return ans;
    }

    private boolean ans = false;

    private char[] charArray;

    private int m;
    private int n;

    private void dfs(char[][] board, int[][] exist, int i, int j, int index) {
        if (ans || index + 1 == charArray.length) {
            ans = true;
            return;
        }
        char val = charArray[index + 1];
        if (i - 1 >= 0 && exist[i - 1][j] == 0 && board[i - 1][j] == val) {
            exist[i - 1][j] = 1;
            dfs(board, exist, i - 1, j, index + 1);
            exist[i - 1][j] = 0;
        }

        if (i + 1 < m && exist[i + 1][j] == 0 && board[i + 1][j] == val) {
            exist[i + 1][j] = 1;
            dfs(board, exist, i + 1, j, index + 1);
            exist[i + 1][j] = 0;
        }

        if (j - 1 >= 0 && exist[i][j - 1] == 0 && board[i][j - 1] == val) {
            exist[i][j - 1] = 1;
            dfs(board, exist, i, j - 1, index + 1);
            exist[i][j - 1] = 0;
        }

        if (j + 1 < n && exist[i][j + 1] == 0 && board[i][j + 1] == val) {
            exist[i][j + 1] = 1;
            dfs(board, exist, i, j + 1, index + 1);
            exist[i][j + 1] = 0;
        }

    }

}
